//////////////////////////////////////
// Fast Container Library           //
// MIT License - Copyright (c) 2012 //
//////////////////////////////////////

#pragma once

#include "common.h"
#include "functional.h"
#include "algobase.h"
#include "heap.h"
#include "merge.h"

// sort.h
//
// sort
// quick_sort
// insertion_sort
// binary_sort
// merge_sort
// stable_sort
// heap_sort			(heap.h)
// partial_sort			(heap.h)
// partial_sort_copy	(heap.h)
// is_sorted
// is_sorted_until

FC_NAMESPACE_BEGIN


namespace internal
{
	template <class BidirectionalIterator, class Compare> inline
	void quick_sort_impl( BidirectionalIterator first, BidirectionalIterator last, Compare compare )
	{
		if( first != last )
		{
			BidirectionalIterator left = first;
			BidirectionalIterator right = --last;
			BidirectionalIterator pivot = left++;

			while( left != right )
			{
				if( compare(*left, *pivot) )
					++left;
				else
				{
					while( left != right && compare(*pivot, *right) )
						--right;
					fc::iter_swap( left, right );
				}
			}

			--left;
			fc::iter_swap( first, left );

			quick_sort_impl<BidirectionalIterator, Compare>( first, left, compare );
			quick_sort_impl<BidirectionalIterator, Compare>( right, last, compare );
		}
	}

	// @very fast median quicksort algorithm taken from http: //homepages.ihug.co.nz/~aurora76/Malc/
	template <class T, class Compare> inline
	void medianquicksortimpl( T* a, int l, int r, Compare compare )
	{
		enum{ Ideal = 16 };
		while (r - l > Ideal)
		{
			int i = (l+r)>>1, j = r-1;
			//pick median of 3 items as splitter
			if (compare(a[i], a[l])) fc::swap(a[i], a[l]);
			if (compare(a[j], a[l])) fc::swap(a[j], a[l]);
			if (compare(a[j], a[i])) fc::swap(a[j], a[i]);
			const T temp = a[i];
			i = l;
			for (;;) //partition items
			{
				do ++i; while (compare(a[i], temp));
				do --j; while (compare(temp, a[j]));
				if (j <= i) break;
				fc::swap(a[i], a[j]);
			}
			if (i-l <= r-i)
			{
				medianquicksortimpl(a, l, i, compare);
				l = i;
			}
			else
			{
				medianquicksortimpl(a, i, r, compare);
				r = i;
			}
		}
	}

	template <class Iter, class T, class Compare> inline
	void insertionsortimpl( Iter first, Iter last, T*, Compare compare )
	{
		for( Iter it = first + 1; it < last; ++it )
		{
			T value = *it;
			Iter next = it;
			for( ; next > first && compare(value, *(next - 1)); --next )
			{
				*next = *(next - 1);
			}
			*next = value;
		}
	}

	template <class Iter, class T> inline
	void insertionsortimpl( Iter first, Iter last, T* )
	{
		for( Iter it = first + 1; it < last; ++it )
		{
			T value = *it;
			Iter next = it;
			for( ; next > first && (value < *(next - 1)); --next )
			{
				*next = *(next - 1);
			}
			*next = value;
		}
	}

	template <class T, class Compare> inline
	void binarysortimpl( T* a, int n, Compare compare )
	{
		for( int i = 1; i < n; ++i )
		{
			int l = 0, r = i, j = i - 1;
			const T tempItem = a[i];
			while (l < r)
			{
				const int m = (l + r) >> 1; //midpoint
				if( compare(tempItem, a[m]) )
					r = m;
				else
					l = m + 1;
			}
			//move items over to make room
			while( j >= l )
			{
				a[j + 1] = a[j];
				--j;
			}

			a[l] = tempItem;
		}
	}


	template <class RandomAccessIterator, class Compare> inline
	void sort( RandomAccessIterator first, RandomAccessIterator last, Compare compare )
	{
		quick_sort_impl( first, last, compare );
	}


	template <class RandomAccessIterator, class Size, class Compare> inline
	void merge_sort_impl( RandomAccessIterator first, RandomAccessIterator last, Size n, Compare compare )
	{
		typename iterator_traits<RandomAccessIterator>::pointer p = 0;
		if( n < 32 )
		{
			insertionsortimpl( first, last, p, compare );
		}
		else
		{
			Size dist = n >> 1;
			RandomAccessIterator mid = first + dist;

			merge_sort_impl<RandomAccessIterator, Size, Compare>( first, mid, dist, compare );
			merge_sort_impl<RandomAccessIterator, Size, Compare>( mid, last, dist, compare );
			fc::inplace_merge<RandomAccessIterator, Compare>( first, mid, last, compare );
		}
	}

	template <class RandomAccessIterator, class Size > inline
	void merge_sort_impl( RandomAccessIterator first, RandomAccessIterator last, Size n )
	{
		typename iterator_traits<RandomAccessIterator>::pointer p = 0;
		if( n < 32 )
		{
			insertionsortimpl( first, last, p );
		}
		else
		{
			Size dist = n >> 1;
			RandomAccessIterator mid = first + dist;

			merge_sort_impl<RandomAccessIterator, Size>( first, mid, dist );
			merge_sort_impl<RandomAccessIterator, Size>( mid, last, dist );
			fc::inplace_merge<RandomAccessIterator>( first, mid, last );
		}
	}

	/*
	template <class RandomAccessIterator, class Size, class T > inline
	void merge_sort_buffer_impl( RandomAccessIterator first, RandomAccessIterator last, Size n, T* buffer )
	{
		typename iterator_traits<RandomAccessIterator>::pointer p = 0;
		if( n < 32 )
		{
			insertionsortimpl( first, last, p );
		}
		else
		{
			Size dist = n >> 1;
			RandomAccessIterator mid = first + dist;

			merge_sort_buffer_impl<RandomAccessIterator, Size>( first, mid, dist );
			merge_sort_buffer_impl<RandomAccessIterator, Size>( mid, last, dist );
			fc::inplace_merge_buffer<RandomAccessIterator>( first, mid, last );
		}
	}
	*/

} //internal


// insertion_sort

template <class Iter, class Compare> inline
	void insertion_sort( Iter first, Iter last, Compare compare )
	{
		internal::insertionsortimpl( first, last, typename iterator_traits<Iter>::pointer(), compare );
	}

template <class Iter> inline
	void insertion_sort( Iter first, Iter last )
	{
		insertion_sort( first, last,
			fc::less<typename iterator_traits<Iter>::value_type>() );
	}


// sort

template <class RandomAccessIterator, class Compare> inline
	void sort( RandomAccessIterator first, RandomAccessIterator last, Compare compare )
	{
		//internal::sort( first, last, compare );
		///*
		ptrdiff_t dist = ptrdiff_t(last - first);
		FC_ASSERT(dist >= 0);

		enum { Ideal = 32 };
		if( dist > Ideal )
			internal::medianquicksortimpl( &*first, 0, dist, compare );

		insertion_sort( first, last, compare );
		//*/
	}

template <class RandomAccessIterator> inline
	void sort( RandomAccessIterator first, RandomAccessIterator last )
	{
		sort( first, last, fc::less<typename iterator_traits<RandomAccessIterator>::value_type>() );
	}


// quick_sort

template <class BidirectionalIterator, class Compare> inline
	void quick_sort( BidirectionalIterator first, BidirectionalIterator last, Compare compare )
	{
		quick_sort_impl( first, last, compare );
	}

template <class BidirectionalIterator> inline
	void quick_sort( BidirectionalIterator first, BidirectionalIterator last )
	{
		quick_sort_impl( first, last,
			less< typename iterator_traits<BidirectionalIterator>::value_type >() );
	}


// binary_sort

template <class RandomAccessIterator, class Compare> inline
	void binary_sort( RandomAccessIterator first, RandomAccessIterator last, Compare compare )
	{
		ptrdiff_t dist = ptrdiff_t(last - first);
		FC_ASSERT(dist >= 0);

		internal::binarysortimpl( &*first, dist, compare );
	}

template <class RandomAccessIterator> inline
	void binary_sort( RandomAccessIterator first, RandomAccessIterator last )
	{
		binary_sort( first, last, 
			less< typename iterator_traits<RandomAccessIterator>::value_type >() );
	}


// merge_sort

template <class RandomAccessIterator, class Compare> inline
	void merge_sort( RandomAccessIterator first, RandomAccessIterator last, Compare compare )
	{
		typedef typename iterator_traits<RandomAccessIterator>::difference_type difference_type;
		const difference_type n = difference_type(last - first);

		internal::merge_sort_impl<RandomAccessIterator, difference_type, Compare>( first, last, n, compare );
	}


template <class RandomAccessIterator> inline
	void merge_sort( RandomAccessIterator first, RandomAccessIterator last )
	{
		typedef typename iterator_traits<RandomAccessIterator>::difference_type difference_type;
		const difference_type n = difference_type(last - first);

		internal::merge_sort_impl<RandomAccessIterator, difference_type>( first, last, n );
	}


// stable_sort

template <class RandomAccessIterator, class Compare> inline
	void stable_sort( RandomAccessIterator first, RandomAccessIterator last, Compare compare )
	{
		merge_sort<RandomAccessIterator, Compare>( first, last, compare );
	}


template <class RandomAccessIterator> inline
	void stable_sort( RandomAccessIterator first, RandomAccessIterator last )
	{
		merge_sort<RandomAccessIterator>( first, last );
	}


// is_sorted_until

template <class ForwardIterator, class Compare> inline
	ForwardIterator is_sorted_until( ForwardIterator first, ForwardIterator last, Compare compare )
	{
		if( FC_LIKELY(first != last) )
			for( ForwardIterator prev = first; ++first != last && !compare(*first, *prev); prev = first ) ;
		return first;
	}

template <class ForwardIterator> inline
	ForwardIterator is_sorted_until( ForwardIterator first, ForwardIterator last )
	{
		if( FC_LIKELY(first != last) )
			for( ForwardIterator prev = first; ++first != last && !(*first < *prev); prev = first ) ;
		return first;
	}


// is_sorted

template <class ForwardIterator, class Compare> inline
	bool is_sorted( ForwardIterator first, ForwardIterator last, Compare compare )
	{
		return is_sorted_until<ForwardIterator, Compare>(first, last, compare) == last;
	}

template <class ForwardIterator> inline
	bool is_sorted( ForwardIterator first, ForwardIterator last )
	{
		return is_sorted_until<ForwardIterator>(first, last) == last;
	}



FC_NAMESPACE_END
